#include <iostream>
#include <fstream>
#include "avl.h"
#include "bst.h"
using namespace std;

int CHECKED;		//A global counter
int IMBALANCES = 0;

int main () {
	int i,						//loop control variable
		num,					//Value to insert or search for
		seed,					//Random number seed
		n,						//Number of values to insert
		compare1, compare2;		//counters for the number of comparisons
								//for lookups
	AvlTree<int> T1;			//The trees
	BinarySearchTree<int> T2;

	ofstream out;				//Output file for the statistics
	out.open("szechy4.txt");		//FIX THE NAME
	out << "Jared Szechy\n";

	//Set up
	cout << "Please enter the seed for the random number generator ";
	cin >> seed;
	out << "Seed = " << seed << endl;
	cout << "How many values do you want to insert? ";
	cin >> n;
	out << "Number of values = " << n << endl;
	srand(seed);

	//Loop to insert random values.
	for (i = 0; i<n; ) 
	{
		num = rand();
		if (!T1.contains(num))
		{
			T1.insert(num);
			T2.insert(num);
			i++;
		}
	}

	//If the trees are small enough, print them
	if (n<=25) 
	{
		out << "AVL Tree Preorder" << endl;
		T1.printTreePre(out);
	}
	if (n<=25) 
	{
		out << "\nBinary Search Tree Preorder" << endl;
		T2.printTreePre(out);
	}

	//Find out the total number of comparisons necessary to do some 
	//look ups
	compare1 = 0;
	compare2 = 0;
	for (i = 0; i<n/2; i++) 
	{
		num = rand();
		T1.contains(num);
		compare1 = compare1 + CHECKED;
		T2.contains(num);
		compare2 = compare2 + CHECKED;
	}

	//Output tree statistics for the AVL tree
	out << "\nAVL statistics following random insertion" << endl;
	out << "-------------------------------------------" << endl;
	out << "Searching for " << n/2 << " values required " << compare1 <<
		" comparisons.\n";
	out << "The avl tree height is " << T1.getHeight() << endl;
	out << "The level of the shallowest is " << T1.Shallowest() << endl;
	out << "The number of leaves is " << T1.numLeaves() << endl;
	out << "The number of nodes with one child is " << T1.numOneChild() << endl;
	out << "The number of nodes with two children is " << T1.numTwoChildren() << endl;
	out << "The average leaf depth is " << T1.avgleafdepth() << endl;
	out << "Of the " << n << " insertions, " << IMBALANCES << " resulted in an imbalance.\n";

	//Output tree statistics for the BST tree
	out << "\nBST statistics following random insertion" << endl;
	out << "-------------------------------------------" << endl;
	out << "Searching for " << n/2 << " values required " << compare2 <<
		" comparisons.\n";
	out << "The BST height is " << T2.getHeight() << endl;
	out << "The level of the shallowest is " << T2.Shallowest() << endl;
	out << "The number of leaves is " << T2.numLeaves() << endl;
	out << "The number of nodes with one child is " << T2.numOneChild() << endl;
	out << "The number of nodes with two children is " << T2.numTwoChildren() << endl;
	out << "The average leaf depth is " << T2.avgleafdepth() << endl;

	cout << "\nProgram Complete\n";
	return 0;
}
